# koroFileHeader at Yungoal acer
# Create: 2021-09-08 09:53:55
# LastEdit: 2021-09-08 13:07:02
"""https://leetcode-cn.com/problems/binary-tree-inorder-traversal/"""
__author__ = '749B'

from typing import List, Optional, TypeVar
Node = TypeVar('Node', bound='TreeNode')


class TreeNode:
    def __init__(self, val: int=0, left: Optional[Node]=None, right: Optional[Node]=None) -> None:
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def inorderTraversal0(self, root: Optional[TreeNode]) -> List[int]:
        """递归算法"""
        if root is None:
            return []
        return self.inorderTraversal0(root.left) + [root.val] + self.inorderTraversal0(root.right)

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """迭代，要利用栈。这个写法不够模板化，无法通用前序、中序、后序"""
        stack: List[TreeNode] = []
        res: List[int] = []
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            if stack:
                p = stack.pop()
                res.append(p.val)
                p = p.right
        return res



        